1. Field of the Invention
The present invention relates to the field of computing and, more particularly, to a technique for concurrently detecting the multiple occurrence of a bit pattern.
2. Background of the Related Art
In data processing, operations that perform pattern detection are utilized to identify the presence of a predefined pattern. One such detection scheme detects the presence of a certain bit or bit sequence in a bit string and, often times, identifies the location of the detected pattern. Detection of such bit patterns allows other operations to be performed, based on the results obtained from the detection. In one scheme, leading one ("1") detection is utilized for detecting the occurrence of the very first "1" bit in a bit string and its associated position (bit location or address) within the bit string. Processing devices, implementing such leading "1" detection circuitry, then utilize the results of the "1" detection to perform other tasks.
For example, in U.S. Pat. No. 5,383,142 (in which the inventor is the same as the inventor in the present application), a technique for detecting the occurrence of a leading "1" is disclosed. Leading "1" detection is implemented to resolve proper normalization of floating point computations. It is also implemented in queuing processor access in a multiple processor computer system. In these instances, the bit location of the leading "1" bit provides the information necessary to perform the task.
However, there are instances in which the detection of the occurrence of the second and subsequent "1" bit is desirable. For example, in a processor architecture where processors execute variable length instructions, the byte length will not be constant for all of the instructions. When these instructions are stored sequentially, the instruction boundaries will not reside at set multiples of a byte address. Thus, in order to identify the start of an instruction boundary, each byte is accessed to determine if it is an opcode, since opcodes are located at the beginning of an instruction. As a further extension to this scheme, instructions are at times pre-decoded, marked as to the instruction boundaries and stored in an instruction cache. Accordingly, to process the variable length instructions, additional time is required to find the instruction boundaries.
As noted above, one technique is to pre-decode and mark the instruction boundaries, so that the instructions can be issued. For example, a "1" bit is utilized to mark the start of each instruction and a scan for the "1" bit will find the start of an instruction. That is, identification of the location of the first "1" identifies the start of the first instruction and the identification of the location of the second "1" identifies the start of the next instruction, etc.
The rapid detection of instruction boundaries allows the processor to find and fetch the next instruction much more quickly and has significant advantages in superscalar processors which use pipelining. It is especially useful for multiple instruction issue, when two or more instructions are to be issued concurrently. The present invention provides a scheme in which the occurrence of the first "1" bit and the second "1" bit can be detected concurrently, so that one application of the invention permits two instruction boundaries to be identified concurrently. The concurrent "1" detection can be extended to locate the occurrence of subsequent "1"s as well. Furthermore, the detection technique can be utilized to detect other bit patterns and is not limited to the detection of a single bit.